/*
 * @lc app=leetcode.cn id=200 lang=cpp
 *
 * [200] 岛屿数量
 */

#include <limits.h>

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// @lc code=start
class Solution {
public:
    int numRow;
    int numColumn;

    int numIslands(vector<vector<char>>& grid) {
        numRow = grid.size();
        if (grid.empty()) return 0;
        
        numColumn = grid[0].size();
        int result = 0;

        for (int i = 0; i < numRow; i++) {
            for (int j = 0; j < numColumn; j++) {
                if (grid[i][j] == '1') {
                    result++;
                    dfs(grid, i, j);
                }   
            }
        }
        
        return result;
    }

    void dfs(vector<vector<char>>& grid, int a, int b) {
        grid[a][b] = '0';

        if (a - 1 >= 0 && grid[a - 1][b] == '1') dfs(grid, a - 1, b);
        if (a + 1 < numRow && grid[a + 1][b] == '1') dfs(grid, a + 1, b);
        if (b - 1 >= 0 && grid[a][b - 1] == '1') dfs(grid, a, b - 1);
        if (b + 1 < numColumn && grid[a][b + 1] == '1') dfs(grid, a, b + 1);
        
        return;
    }
};
// @lc code=end

